'''
https://leetcode.cn/problems/satisfiability-of-equality-equations/?envType=study-plan-v2&envId=graph-theory
'''
from typing import List

class UF:
    def __init__(self, n):
        self.father = list(range(n))
    def find(self, x):
        if x != self.father[x]:
            self.father[x] = self.find(self.father[x])
        return self.father[x]
    def is_same_set(self,x, y):
        return self.find(x) == self.find(y)
    def union(self, x, y):
        fx, fy = self.find(x), self.find(y)
        if fx != fy:
            self.father[fy] = fx

class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        equations.sort(key=lambda x: x[1], reverse=True)
        uf = UF(26)
        for equation in equations:
            a, b = equation[0], equation[3]
            a, b = ord(a) - ord('a'), ord(b) - ord('a')
            if equation[1] == '=':
                uf.union(a, b)
            else:
                if uf.is_same_set(a, b):
                    return False
        return True
